#include <math.h>
#include <mpi.h>
#include <stdio.h>
#include "common.h"
#include "graph.h"
#include "array.h"
#include "triangulacja.h"






Graph trisToGraph(Dane verts, int* indices, int numTris) {
	int i, j, tri, off;
	int i1, i2;
	double dist, tmp;
	Graph res;

	res.numNodes = verts.n;
	res.nodes = new(Node, res.numNodes);
	res.dists = new(double, res.numNodes);
	res.prev = new(int, res.numNodes);

	for (i = 0; i < res.numNodes; ++i) {
		res.nodes[i].numConns = 0;
		res.nodes[i].conns = null;
		res.nodes[i].connDists = null;
		res.dists[i] = dist_max;
		res.prev[i] = -1;
	}

	for (tri = 0; tri < numTris; ++tri) {
		off = tri * 3;
		
		for (i = off; i < off+3; ++i) {
			for (j = off; j < off+3; ++j) {
				if (i == j) continue;

				i1 = indices[i];
				i2 = indices[j];

				if (!alreadyConnected(res, i1, i2)) {
					dist = 0;

							tmp = (verts.vert[i1].x - verts.vert[i2].x);
							tmp *= tmp;
					dist += tmp;

							tmp = (verts.vert[i1].y - verts.vert[i2].y);
							tmp *= tmp;
					dist += tmp;

					dist = sqrt(dist);

					graphNodeConnect(&res.nodes[i1], i2, dist);
					graphNodeConnect(&res.nodes[i2], i1, dist);
				}
			}
		}
	}

	return res;
}



int triangulation(Dane dane, int rank, int size, int* buf){
	int i, j, k, l, m;
	double xn, yn, zn;
	int flag;
	div_t result;
	double *z;

	if(rank != 0)
		dane.vert = new(Vertex, dane.n);

	z = new(double, dane.n);

	if(rank == 0)
		for (i = 0; i < dane.n; i++)
			z[i] = dane.vert[i].x*dane.vert[i].x + dane.vert[i].y*dane.vert[i].y;

	// Rozeslanie wektorow
	MPI_Bcast(&dane.vert[0].x, 2*dane.n, MPI_DOUBLE, 0, MPI_COMM_WORLD);
	MPI_Bcast(z, dane.n, MPI_DOUBLE, 0, MPI_COMM_WORLD);

	// Obliczenia
	l = 0;
	for (i = 0; i < dane.n - 2; i++) {
		result = div(i, size);
		if (result.rem == rank) {
			/* printf("Master testing point %d.\n", i); */
			for (j = i + 1; j < dane.n; j++) {
				for (k = i + 1; k < dane.n; k++) {
					if (j != k) {
						zn = (dane.vert[j].x-dane.vert[i].x) * (dane.vert[k].y-dane.vert[i].y) - (dane.vert[k].x-dane.vert[i].x) * (dane.vert[j].y-dane.vert[i].y);
						flag = (zn < 0);
						if (flag) {
							xn = (dane.vert[j].y-dane.vert[i].y) * (z[k]-z[i]) - (dane.vert[k].y-dane.vert[i].y) * (z[j]-z[i]);
							yn = (dane.vert[k].x-dane.vert[i].x) * (z[j]-z[i]) - (dane.vert[j].x-dane.vert[i].x) * (z[k]-z[i]);
							for (m = 0; m < dane.n; m++)
								flag = flag && ((dane.vert[m].x-dane.vert[i].x) * xn + (dane.vert[m].y-dane.vert[i].y) * yn + (z[m]-z[i]) * zn <= 0);
						}
						if (flag) {
							/*printf("Slave %d: triangle %d %d %d\n", rank, i, j, k);*/
							buf[l + 0] = i;
							buf[l + 1] = j;
							buf[l + 2] = k;
							l+=3;
						}
					}
				}
			}
		}
	}
	return l;
}




